#pragma once

#include <set>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// Grafo implementado utilizando conjuntos
template<typename V = char, typename E = char>
class SetGraph
{
  struct Node 
  {
    int id;
    V value;

    bool operator==(const Node &other) const
    {
      return id == other.id;
    }   
  };

  vector<Node> _nodes;

  struct Edge
  {
    int node1;
    int node2;
    E value;

    bool operator==(const Edge &other) const
    {
      return node1 == other.node1 && node2 == other.node2;
    }
  };

  vector<Edge> _edges;

  struct Pair
  {
    Pair(int max, int min): max(max), min(min) 
    {
    }
    int max;
    int min;
  };

  Pair makePair(int node1, int node2) const
  {
    return node1 > node2 ? Pair(node1, node2) : Pair(node2, node1);
  }

public:
  int addNode(const V &value = V())
  {
    int id = _nodes.size();
    _nodes.push_back({id,value});
    return id;
  }

  const V &getNodeValue(int n) const
  {
    return _nodes[n].value;
  }

  int countNodes() const
  {
    return _nodes.size();
  }

  int getNodeDegree(int node) const
  {
    int d = 0;
    for (auto edge: _edges) {
      if (edge.node1 == node || edge.node2 == node) {
        d++;
      }
    }
    return d;
  }

  int countEdges() const
  {
    return _edges.size();
  }

  bool isAValidNode(int id)
  {
    Node node {id,V()};
    return find(_nodes.begin(), _nodes.end(),node) != _nodes.end();
  }

  bool addEdge(int node1, int node2, const E &value = E())
  {
    // verifica se os vértices existem
    if (node1 == node2 || !isAValidNode(node1) || !isAValidNode(node2)) {
      return false;
    }

    Pair pair = makePair(node1, node2);

    _edges.push_back({pair.max, pair.min,value});

    return true;
  }
  
  bool areNodesAdjacents(int node1, int node2)
  {
    Pair pair = makePair(node1, node2);
    
    Edge edge {pair.max, pair.min, E()};

    return find(_edges.begin(), _edges.end(), edge) != _edges.end();
  }
  
  const E &getEdgeValue(int node1, int node2) const
  {
    Pair pair = makePair(node1, node2);
  
    Edge edge {pair.max, pair.min, E()};

    return find(_edges.begin(), _edges.end(),edge)->value;
  }

  vector<int> getAdjacentNodes(int node) const
  {
    vector<int> a;

    for (auto edge: _edges) {
      if (edge.node1 == node) {
        a.push_back(edge.node2);
      } else if (edge.node2 == node) {
        a.push_back(edge.node1);
      }
    } 

    return a;
  }
};
